package com.bclz.leetcode

import java.util
import java.util.Map.Entry
import java.util.function.Predicate
import java.util.{Comparator, PriorityQueue}

import scala.annotation.tailrec


object LeetcodePractise {


  def main(args: Array[String]): Unit = {
    //    println(Solution.addBinary("11111010101010100101101010","1010101010101010101011"))
    //    println(Solution.addDigits(120))
    //    println(Solution.addStrings("11","99"))
    //    println(Solution.addToArrayForm(Array(2,1,5),806))
    //    println(Solution.arrangeCoins(1804289383))
    //    println(Math.sqrt(0.25+2*1))
    //    println(Solution.arrayPairSum((0 to 10000).toArray))
    //    println(Solution.bubbling(Array(2,4,1,6,99,44,10,45),false).foreach(println(_)))
//    println(Solution.binarySearch(Array(1, 3, 4, 5, 6, 7), 2))

//    val arr = Array(4,5,8,2)
//    val kthLargest = new KthLargest(3, arr)
//    println(kthLargest.add(3))
//    println(kthLargest.add(5))
//    println(kthLargest.add(10))
//    println(kthLargest.add(9))
//    println(kthLargest.add(4))

//    println(Solution.topKFrequent(Array("i", "love", "leetcode","leetcode","leetcode","leetcode", "i", "love","coding"),3))

//      println(Solution.isAnagram("",""))
//    println(Solution.twoSum2(Array(2,7,11,15),9).foreach(println(_)))
    val a=Array(3,2)
    quickSort(a)
    println(a.toList)
  }

  object Solution {


    /**
      *
      * @param a
      * @param b
      * @return
      */
    def addBinary(a: String, b: String): String = {
      val longStr = if (a.length > b.length) a else b
      val shortStr = if (a.length > b.length) b else a
      val max = longStr.length
      val min = shortStr.length

      @tailrec
      def addBinary2(result: String, i: Int, isCarry: Boolean): String = {
        if (i < 0 && (max - min + i) < 0) if (isCarry) 1 + result else result
        else {
          val value = (longStr.charAt(max - min + i) - '0') + (if (i > -1) (shortStr.charAt(i) - '0') else 0) + (if (isCarry) 1 else 0)
          if (value % 2 == 0 && value != 0) addBinary2(0 + result, i - 1, true)
          else if (value / 2 >= 1) addBinary2(1 + result, i - 1, true)
          else addBinary2(value + result, i - 1, false)
        }

      }

      addBinary2("", min - 1, false)

    }

    /**
      * 38->2    :   3+8->11->2
      *
      * @param num
      * @return
      */
    @tailrec
    def addDigits(num: Int): Int = {
      if (num < 10) num
      else {
        val str = num.toString
        val value = (0 to (str.length - 1)).map(i => str.substring(i, i + 1).toInt).reduce(_ + _)
        addDigits(value)
      }
    }

    /**
      * 时间复杂度O(1)实现
      *
      * @param num
      * @return
      */
    def addDigits2(num: Int): Int = {
      if (num < 9) num
      else if (num % 9 == 0) 9
      else num % 9
    }

    /**
      * 字符串相加
      *
      * @param num1
      * @param num2
      * @return
      */
    def addStrings(num1: String, num2: String): String = {
      val maxStr = if (num1.length > num2.length) num1 else num2
      val minStr = if (num1.length > num2.length) num2 else num1
      val maxLength = maxStr.length
      val minLength = minStr.length

      def recur(i: Int, result: String, isCarry: Boolean): String = {
        val maxIndex = maxLength - minLength + i
        val addResult = (maxStr.charAt(maxIndex) - '0') + (if (i > -1) minStr.charAt(i) - '0' else 0) + (if (isCarry) 1 else 0)
        if ((maxLength - minLength + i) <= 0)
          addResult + result
        else {
          val jointStr = addResult % 10 + result
          recur(i - 1, jointStr, if (addResult / 10 > 0) true else false)
        }

      }

      recur(minLength - 1, "", false)
    }

    /**
      * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
      * 例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
      * 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
      * 输入：A = [1,2,0,0], K = 34
      * 输出：[1,2,3,4]
      * 解释：1200 + 34 = 1234
      *
      * @param A
      * @param K
      * @return
      */
    def addToArrayForm(A: Array[Int], K: Int): List[Int] = {
      def recur(i: Int, isCarry: Boolean, k: Int, l: List[Int]): List[Int] = {
        val addValue = k % 10 + (if (i > -1) A(i) else 0) + (if (isCarry) 1 else 0)
        if (k == 0 && i < 0) if (isCarry) 1 :: l else l
        else recur(i - 1, addValue / 10 >= 1, k / 10, addValue % 10 :: l)
      }

      recur(A.length - 1, false, K, Nil)
    }

    def arrangeCoins(n: Int): Int = {
      //      @tailrec
      //      def recur(remainNum:Int,line:Int):Int={
      //        if(line==remainNum) line
      //        else if(line>remainNum) line-1
      //        else recur(remainNum-line,line+1)
      //      }
      //
      //      recur(n,1)

      //第二种数学推导，需要避免int 大于2^31-1 的情况
      Math.floor(Math.sqrt(0.25 + 2 * n.toLong) - 0.5).toInt

    }

    def arrayPairSum(nums: Array[Int]): Int = {

      val numInSorted = nums.sorted
      (0 to numInSorted.length - 1).filter(i => (i & 1) == 0).map(numInSorted(_)).sum
    }


    /**
      * 冒泡
      *
      * @param nums
      * @return
      */
    def bubbling(nums: Array[Int], asc: Boolean): Array[Int] = {

      for (i <- 0 until nums.length if (i != nums.length - 1)) {
        for (j <- i + 1 until nums.length) {

          if (nums(i) < nums(j) && !asc || nums(i) > nums(j) && asc) {
            val temp = nums(i)
            nums(i) = nums(j)
            nums(j) = temp
          }

        }
      }
      nums
    }


    def binarySearch(nums: Array[Int], num: Int): Int = {


      def recursion(start: Int, end: Int): Int = {
        if (start > end) return -1

        val mid = (start + end) >> 1

        if (num > nums(mid)) {
          recursion(mid + 1, end)
        } else if (num < nums(mid)) {
          recursion(start, mid - 1)
        } else {
          mid
        }
      }

      recursion(0, nums.length - 1)
    }

    /**
      * 703.设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
      * 二叉堆解法(优先队列)
      * 采用Min-Heap:  维护一个大小为k的堆，栈顶元素就是k个元素中最小，第k大
      * @param _k
      * @param _nums
      */
    class KthLargest(_k: Int, _nums: Array[Int]) {


      var size = _nums.length
      var elements: Array[Int] = _nums
      buildBinaryHeap()
      while(size>_k){
          dequeue()
      }

      def add(`val`: Int): Int = {
        enqueue(`val`)
        if(size>_k){
          dequeue()
        }
        elements(0)
      }

      def enqueue(ele:Int):Unit ={
        if(size>=elements.size){
          resize()
        }
        elements(size)=ele
        size=size+1
        upAdjust(size-1)
      }

      def dequeue(): Int ={

        val deEle=elements(0)
        elements(0)=elements(size-1)
        elements(size-1)=0
        size=size-1
        downAdjust(0)
        deEle
      }

      def buildBinaryHeap(): Unit = {

        val noChildrenNodeIndex = size / 2
        var i = noChildrenNodeIndex
        while (i >= 0) {
          downAdjust(i)
          i = i - 1
        }

      }

      def downAdjust(i: Int): Unit = {
        val leftNodeIndex = 2 * i + 1
        if (leftNodeIndex >= size) return
        val rightNodeIndex = 2 * i + 2
        val minIndex = if (rightNodeIndex >= size) leftNodeIndex else (if (elements(leftNodeIndex) > elements(rightNodeIndex)) rightNodeIndex else leftNodeIndex)
        val minVal = elements(minIndex)
        if (minVal < elements(i)) {
          elements(minIndex) = elements(i)
          elements(i) = minVal
          downAdjust(minIndex)
        }

      }

      def upAdjust(i: Int): Unit = {

        val headIndex = if ((i & 1) == 0) (i - 2) / 2 else (i - 1) / 2
        if (headIndex < 0) return
        if (elements(i) < elements(headIndex)) {
          val temp = elements(i)
          elements(i) = elements(headIndex)
          elements(headIndex) = temp
          upAdjust(headIndex)
        }
      }

      def resize() = {
        val oldSize = elements.length
        val newSize = 2 * oldSize+1
        elements = util.Arrays.copyOf(elements, newSize)

      }


    }


    /**
      * 692.给一非空的单词列表，返回前 k 个出现次数最多的单词。
      * 时间复杂度O（nlogn）,空间复杂度O（n）
      *
      * for循环遍历 n
      * 优先队列内部二叉树实现时间复杂度位nlogn
      * 循环 k
      * 并列关系时间复杂度位nlogn
      * @param words
      * @param k
      * @return
      */
    def topKFrequent(words: Array[String], k: Int): List[String] = {

      val wordCountMap=new util.HashMap[String,Int]()
      for(i <- 0 until words.length){

        val str = words(i)
        wordCountMap.put(str,wordCountMap.getOrDefault(str,0)+1)

      }
      val priQueue=new PriorityQueue[String](new Comparator[String] {
        override def compare(o1: String, o2: String): Int =
          if((wordCountMap.get(o2)-wordCountMap.get(o1))==0) o1.compareTo(o2) else (wordCountMap.get(o2)-wordCountMap.get(o1))
      })
      priQueue.addAll(wordCountMap.keySet())

      val level=Math.min(k,priQueue.size())
      val result = for (i <- 0 until  level) yield priQueue.poll()

      return result.toList
    }


    /**
      * 242.给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
      * eg:   s = "anagram", t = "nagaram"     =>  true
      *        s = "rat", t = "car"    =>  false
      * @param s
      * @param t
      * @return
      */
    def isAnagram(s: String, t: String): Boolean = {
      val charHash=new util.HashMap[Char,Integer]()
      for (i <- 0 until Math.max(s.length,t.length)){

        if(i<s.length){
          val sc = s.charAt(i)
          charHash.put(sc,charHash.getOrDefault(sc,0)+1)
        }

        if(i<t.length){
          val tc = t.charAt(i)
          charHash.put(tc,charHash.getOrDefault(tc,0)-1)
        }

      }
      return charHash.entrySet().stream().noneMatch(new Predicate[Entry[Char,Integer]]() {
        override def test(t: Entry[Char, Integer]): Boolean = t.getValue!=0
      })
    }


    /**
      * 1 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
      * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
      * 1. 循环，时间复杂度O（n^2）,空间复杂度O（1）
      * 2. hash表解决，时间复杂度O（n）,空间复杂度O（n）
      * @param nums
      * @param target
      * @return
      */
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {

        for(i <- 0 until nums.length){
              for(j <- 0 until nums.length if(i!=j)){
                        if(nums(i)+nums(j)==target){
                          return Array(i,j)
                        }
              }
        }
        return Array()
    }

    def twoSum2(nums: Array[Int], target: Int): Array[Int] = {
      import java.util._
      val numMap=new HashMap[Int,Int]()
      for(i <- 0 until nums.length){
          if(numMap.containsKey(target-nums(i))){
            return Array(numMap.get(target-nums(i)),i)
          }
          numMap.put(nums(i),i)
      }
      return Array()
    }

    /**
      * 15.三数之和
      * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
      *
      * 1.循环  时间O（n^3）
      * 注意：答案中不可以包含重复的三元组。
      *
      *
      * @param nums
      * @return
      */
    def threeSum(nums: Array[Int]): List[List[Int]] = {
      import java.util.HashSet
      import scala.collection.mutable.ListBuffer
      val result = new ListBuffer[List[Int]]
      val numsSet=new HashSet[Int]()
      for (i <- 0 until nums.length){
        numsSet.add(nums(i))
      }

      for (i <- 0 until nums.length-1){
        for (j <- i+1 until nums.length){
          val numsI=nums(i)
          val numsJ=nums(j)
          val thirdNums=(-(numsI+numsJ))
          if(numsSet.contains(thirdNums)&&numsI!=thirdNums&&numsJ!=thirdNums){
            val ints = List(numsI,numsJ,-(numsI+numsJ))
            result+=ints
          }

        }
      }

    return result.toList

    }


  }


  def  quickSort(array:Array[Int]){
      def swap(array: Array[Int],i1:Int,i2:Int): Unit ={
        val temp=array(i1)
        array(i1)=array(i2)
        array(i2)=temp
      }

      def quickSort(array: Array[Int],left:Int,right:Int): Unit ={
        if(left>=right){
          return
        }
        val base=array(left)
        var index=left+1
        for(i <- (index to right )){
          if(array(i)<base){
            swap(array,index,i)
            index=index+1
          }
        }
        swap(array,left,index-1)
        quickSort(array,left,index-2)
        quickSort(array,index,right)

      }

    quickSort(array,0,array.length-1)



  }

}
